package 图.树;

import org.junit.Test;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;

/**
 * @author aodre , QQ : 480029069
 * @date 2023/6/8 9:22
 */
public class lc2467树上得最大得分和路径 {
    /*
     无环图得 dfs 首先要会 ， 这对于 递归 非常熟悉得你来说， 不是小事一桩嘛！
     关键是,建图的方式
     */

    public int mostProfitablePath(int[][] edges, int bob, int[] amount) {
        // 邻接表的方式来 建图
        ArrayList<Integer> [] graph = new ArrayList[edges.length];
        //  建图
        for(int i = 0;i < edges.length;i++){
            for(int j = 0;j < edges[0].length;i++){
                graph[edges[i][0]].add(edges[i][1]);
            }
        }
        // 无向图， 得 整个 数组 记录一下， 当前node 在一条之路 走没走过， 防止死循环
        boolean used[] = new boolean[edges.length];
        // 先把 根节点 放进来！
        used[0] = true;

        return 0;
    }
    // 传入 图的   起点， 以及 图本身
    public int dfs(int node, ArrayList<Integer> [] graph,boolean used[],int []amount){
        //  basecase 是什么， 就是当前node 没有子节点
        // 但是问题在于， 这 tm 是无向图（无环）
        // 当前 节点只有一个 子节点， 而且子节点， 已经走过 ，说明这是 叶子节点， 仅靠 size == 0 是无法判断叶子节点 的 ， 比如 根节点
        if(graph[node].size() == 1 && used[graph[node].get(0)]){
            return amount[node];
        }
        // 开始 dfs
        int ans = 0;
        for(int no : graph[node]){
            if(!used[no]){
                used[no] = true;
                ans = Math.max(dfs(no,graph,used,amount),ans);
                used[no] = false;
            }
        }
        return ans + amount[node];
    }


    /*
     哈希表的 建图方式！
     */


    public int solution(int edges[][],int bob,int amount[]){
        HashMap<Integer,List<Integer>> graph = new HashMap<>(amount.length);
        for(int []edge : edges){
            graph.computeIfAbsent(edge[0],t -> new ArrayList<>()).add(edge[1]);
            // 无向图
            graph.computeIfAbsent(edge[1],t -> new ArrayList<>()).add(edge[0]);
        }

        boolean used[] = new boolean[amount.length];
        int map[] = new int[amount.length];
        Arrays.fill(map,amount.length);
        bobToNode(used,graph,map,bob,0);
        System.out.println(Arrays.toString(map));
        return dfsAlice(0,new boolean[amount.length],graph,map,0,amount);
    }

    /*
     无向图， 记录 一下 bob 到达 0 节点过程中，  time  ---> 对应的  node
                                          node ----> 对应的 time
                                      记录这两个其实是一样的 结果!
     */
    // f() 函数的 含义: 能否 能从 当前node 达到 0 节点,  能 true ,否 返回 false
        public boolean bobToNode(boolean []used,HashMap<Integer,List<Integer>> graph,int []map,int node,int curTime){
            if(node == 0){
                map[node] = curTime;
                return true;
            }
            used[node] = true;
            for(int no : graph.get(node)){ // 因为 不存在 ** 环 ** , 所以只有一条 路径, bob --> 0. 所以 找到一条直接返回就行了
                if(!used[no] && bobToNode(used,graph,map,no,curTime+ 1 )){ // 找到路径了
    //                map[no] = curTime;
                    map[node] = curTime;
                    return true;
                }
                map[no] = Integer.MAX_VALUE;
            }
            return false;
        }

    /*
     这里 有一个 非常恶心的点:
     就是 叶子节点(除了  根节点,  因为在 该题 中, 根节点很有可能也会 被当成 叶子节点) 应该
     */
    public int dfsAlice(int node,boolean used[],HashMap<Integer,List<Integer>> graph,int []map,int curTime,int amount[]){

        used[node] = true;
        int ans = Integer.MIN_VALUE;
        for(int no : graph.get(node)){
            if(!used[no]){
                ans = Math.max(ans,dfsAlice(no,used,graph,map,curTime + 1,amount));
            }
        }
//        if(ans == Integer.MIN_VALUE){ // 说明是叶子节点 直接返回 当前节点的 amount
//            return amount[node];
//        }
//        return ans + (map[node] == curTime ? amount[node] / 2 : amount[node]);
//        return ans + (map[node] == curTime ? amount[node] / 2 : map[node] < curTime ? 0 : amount[node]);
        return (ans == Integer.MIN_VALUE ? 0 : ans) + (map[node] == curTime ? amount[node] / 2 : map[node] < curTime ? 0 : amount[node]);
    }








    @Test
    public void test(){
      String s =   "[[0,1],[1,2],[1,3],[3,4]]";
        String replace = s.replace('[', '{');
        String replace1 = replace.replace(']', '}');
        System.out.println(replace);
        System.out.println(replace1);

        int edges[][] = {{0,1},{1,2},{1,3},{3,4}};
        int amout [] = {-2,4,2,-4,6};
        int solution = solution(edges, 3, amout);
        System.out.println(solution);

    }















    /*
     arignote 的做法
     主要是图 的一个 遍历方式
     */
    public int mostProfitablePathArignote(int[][] edges, int bob, int[] amount) {
        HashMap<Integer, ArrayList<Integer>> map = new HashMap<>();
        for (int[] edge : edges) {
            map.computeIfAbsent(edge[0], t -> new ArrayList<>()).add(edge[1]);
            map.computeIfAbsent(edge[1], t -> new ArrayList<>()).add(edge[0]);
        }
        int[] dist = new int[amount.length];
        mostProfitablePath(Integer.MIN_VALUE, bob, -1, dist, new boolean[amount.length], map);
        return mostProfitablePath(Integer.MIN_VALUE, 0, -1, dist, amount, map);
    }

    private boolean mostProfitablePath(int i, int bob, int j, int[] dist, boolean[] visited,
                                       HashMap<Integer, ArrayList<Integer>> map) {
        if (!visited[bob]) {
            dist[bob] = bob > 0 ? dist[bob] : i;
            for (int k : map.get(bob)) {
                dist[bob] = k != j && mostProfitablePath(i + 1, k, bob, dist, visited, map) ? i : dist[bob];
            }
        }
        return dist[bob] < 0;
    }

    private int mostProfitablePath(int i, int j, int k, int[] dist, int[] amount,
                                   HashMap<Integer, ArrayList<Integer>> map) {
        int max = Integer.MIN_VALUE;
        for (int l : map.get(j)) {
            max = Math.max(max, l == k ? Integer.MIN_VALUE : mostProfitablePath(i + 1, l, j, dist, amount, map));
        }
        return (max > Integer.MIN_VALUE ? max : 0) + (i > dist[j] ? 0 : amount[j] / (i < dist[j] ? 1 : 2));
    }





}
